package 分割回文串;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/14 17:19
 * @description: 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 * 返回 s 所有可能的分割方案。
 * 示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
 */
public class Solution {
    public List<List<String>> partition(String s) {
        // 切割问题类似组合问题
        // 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....
        // 回溯的参数：s, startIndex, path, result
        // 回溯的返回值：void
        // 回溯的终止条件：切割的不是回文 或者 串s被完全切割(startIndex > length)
        // 单层回溯的逻辑：
        // 横向通过for循环遍历串s,每次的起始索引索要加1，这样就避免了字串重复，截取的范围是 startIndex --> i
        // 纵向遍历后续的字串，每递归一个树的分支就是代表截取的字串是不同的，startIndex --> i 即截取的分支
        // 如果他是回文串，那么下一次回文串的开始位置是 i + 1
        /*
         切割问题可以抽象为组合问题：
         如何模拟那些切割线？？？？
         切割问题中递归如何终止？？？？
         在递归循环中如何截取子串？？？？
         如何判断回文？？？？
        */
        length = s.length();
        backtarcking(s, 0);
        return result;
    }

    private List<List<String>> result = new ArrayList<>();
    private List<String> path = new ArrayList<>();
    private int length;

    public void backtarcking(String s, int startIndex) {
        if (startIndex >= length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < length; i++) {
            // 左闭右开
            if (judge(s, startIndex, i + 1)) {
                // 当前串是回文串，加入到 path 中, 左闭右开
                path.add(s.substring(startIndex, i + 1));
                // 递归
                backtarcking(s, i + 1);
            } else {
                continue;
            }
            // 回溯
            path.remove(path.size() - 1);
        }
    }

    public boolean judge(String s, int left, int right) {
        // 床过来的参数是 左闭右开 的
        right = right - 1;
        for (int i = left, j = right; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }


}
